package array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，
 * 使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
 *
 * 注意：答案中不可以包含重复的三元组。
 *
 */
public class leetCode15_threeSum {

    public static void main(String[] args) {
        int[] a = {1,-1,-1,0};
        leetCode15_threeSum b = new leetCode15_threeSum();
        List<List<Integer>> lists = b.threeSum(a);
        System.out.println(1);
    }

    public List<List<Integer>> threeSum(int[] nums) {
        if(nums == null || nums.length == 0) return new ArrayList<>();
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            if(nums[i] > 0) return result;
            if(i > 0 && nums[i] == nums[i - 1]){
                continue;
            }

            int j = i + 1;
            int k = nums.length - 1;
            while (j < k){
                if(nums[i] + nums[j] + nums[k] > 0){
                    k--;
                }else if(nums[i] + nums[j] + nums[k] < 0){
                    j++;
                }else{
                    List<Integer> item = new ArrayList<>();
                    item.add(nums[i]);
                    item.add(nums[j]);
                    item.add(nums[k]);
                    result.add(item);
                    while (j < k && nums[j] == nums[j + 1]){
                        j++;
                    }
                    while (j < k && nums[k] == nums[k - 1]){
                        k--;
                    }
                    j++;
                    k--;
                }
            }

        }

        return result;

    }

    public void quickSort(int[] nums,int left,int right){
        if(left >= right){
            return;
        }

        int mid = findMid(nums,left,right);
        quickSort(nums,left,mid - 1);
        quickSort(nums,mid + 1,right);

    }

    public int findMid(int[] nums,int l,int r){
        int base = nums[l];
        int left = l;
        int right = r;

        while (left < right){
            while (left < right && nums[right] > base){
                right--;
            }
            while(left < right && nums[left] <= base){
                left++;
            }
            if(left < right){
                int tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp;
            }
        }
        nums[l] = nums[left];
        nums[left] = base;
        return left;
    }

    public void quickSort2(int[] nums, int start, int end){
        if(start > end){
            return;
        }
        int partition = partition(nums, start, end);
        quickSort2(nums,partition + 1,end);
        quickSort2(nums, start,partition - 1);

    }
    public int partition(int[] nums, int left, int right){
        int base = nums[left];
        int l = left;
        int r = right;
        while (l < r){
            while (l < r && nums[r] > base){
                r--;
            }
            while (l < r && nums[l] <= base){
                l++;
            }
            if(l < r){
                swap(nums,l,r);
            }
        }
        swap(nums,left,l);
        return l;
    }

    public void swap(int[] nums,int a,int b){
         int tmp = nums[a];
         nums[a] = nums[b];
         nums[b] = tmp;
    }
}






